#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

// 函数：找零最少硬币个数
int findMinCoins(vector<int>& coins, int target) {
    int n = coins.size();
    vector<int> dp(target + 1, INT_MAX); // 动态规划数组，初始值为INT_MAX
    dp[0] = 0; // 0元的找零个数为0

    for (int i = 1; i <= target; i++) {
        for (int j = 0; j < n; j++) {
            // 如果当前硬币面值小于等于目标值i，并且dp[i - coins[j]]不为INT_MAX
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                // 更新dp[i]为dp[i - coins[j]] + 1和当前dp[i]的较小值
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }

    return dp[target]; // 返回目标值的最少硬币个数
}

int main() {
    int n; // 硬币种类数
    vector<int> coins; // 硬币面值数组
    int target; // 目标值

    // 从文件中读取输入数据
    ifstream input_file("input.txt"); // 打开输入文件
    if (input_file.is_open()) {
        input_file >> n; // 读取硬币种类数
        coins.resize(n); // 调整硬币面值数组大小
        for (int i = 0; i < n; i++) {
            input_file >> coins[i]; // 读取每个硬币的面值
        }
        input_file >> target; // 读取目标值
        input_file.close(); // 关闭输入文件

    } else {
        cout << "无法打开输入文件" << endl; // 打开失败，输出错误信息
        return 1; // 返回错误代码
    }

    // 计算最少硬币个数
    int result = findMinCoins(coins, target);

    // 将结果写入文件
    ofstream output_file("output.txt"); // 打开输出文件
    if (output_file.is_open()) {
        output_file << result << endl; // 将结果写入文件
        cout << "最少硬币数量为：" ; // 输出结果到控制台
        cout << result << endl; // 输出结果到控制台
        output_file.close(); // 关闭输出文件
        cout << "已写入文件output.txt" << endl; // 输出成功信息
    } else {
        cout << "无法打开输出文件" << endl; // 打开失败，输出错误信息
        return 1; // 返回错误代码
    }

    return 0; // 返回正常退出代码
}